1. Field of the Invention
The present invention relates to a detection of errors in data and, more particularly, to an error detector for detecting errors that occur in data under transmission.
The present invention relates to a semiconductor device comprising the error detector.
The present invention relates to an error detection method for detecting errors that occur in data under transmission.
2. Description of the Related Art
There are various factors which may cause errors in data being transmitted via transmission lines. For the detecting the errors, a transmitter in a communication system adds check data, under a given rule, to target data to be transmitted. A receiver in the communication system examines whether or not the transmitted data is in accordance with the rule and judges whether or not there are the presence of errors based on the result of the detection.
Out of error detection methods, the most prevalent one is a CRC (Cyclic Redundancy Check) method using a cyclic code. In the CRC error detection, the transmitter splits the target data to be transmitted into information bit strings of a specified length, represents each of the information bit strings in a polynomial, and divides it by a generator polynomial. The transmitter then generates the cyclic code by adding, as check bits, a remainder from the division to the information bit string and transmits the cyclic code to the receiver.
The receiver divides the received cyclic code by the same generator polynomial used at the transmitter to judge whether or not the presence of errors depending on whether or not the cyclic code is divisible.
FIG. 1 shows an exemplary communication system that performs the error detection by using the cyclic code. In the communication system, a transmitter 1, and a receiver 2 are connected to each other via a radio transmission line 3. The transmitter 1 and the receiver 2 correspond to, e.g., a base station and a mobile terminal for mobile communication such as a mobile phone, respectively.
The transmitter 1 has a coder 4 for coding data to be transmitted and a data modulating/transmitting unit 5 for modulating the coded data and outputting the modulated data to the radio transmission line 3. The coder 4 is composed of a feedback shift register 6.
The receiver 2 has a data receiving/demodulating unit 7 for receiving the data transmitted via the radio transmission line 3 and demodulating the received data, and an error detector 8 for detecting errors in the demodulated data. The error detector 8 is composed of a feedback shift register 9 and an right/wrong output unit 10 for outputting an error detecting signal FLAG. The error detector 8 has been formed in a semiconductor device SEM with other communication functional elements.
As shown in FIG. 2, the feedback shift register 6 and the feedback shift register 9 are composed of identical circuits such as dividers conforming to a sixteenth-degree generator polynomial X16+X12+X5+1.
Each of the feedback shift registers 6 and 9 has a register unit 11 consisting of flip-flop circuits X15 to X0 (hereinafter referred to as F/F circuits X15 to X0) connected in cascade, three EOR (Exclusive OR) circuits 12a, 12b, and 12c, and switches S1 and S2. In the register unit 11, a shift direction has been set such that data is shifted from the F/F circuit X0 to the F/F circuit X15. A clock signal CLK is connected to the clock terminal of each of the F/F circuits X15 to X0 such that shift operations are performed in synchronization.
The EOR circuit 12a receives an output of the F/F circuit X15 and an input signal DIN1 (or DIN2) and outputs the result of the operation to the F/F circuit X0. The EOR circuit 12b receives the output of the EOR circuit 12a and an output of the F/F circuit X11 and outputs the result of the operation to the F/F circuit X12. The EOR circuit 12c receives the output of the EOR circuit 12a and an output of the F/F circuit X4 and outputs the result of the operation to the F/F circuit X5.
The switch S1 is for selectively connecting the output of the F/F circuit X15 or the input signals DIN1 and DIN2 to the output signals DOUT1 and DOUT2 of the feedback shift registers 6 and 9. The switch 2 is for feeding back the output of the EOR circuit 12a to the EOR circuits 12b and 12c and to the F/F circuit X0.
In the communication system shown in FIG. 1, the transmitter 1 performs coding and the receiver 2 performs the error detection as follows. By way of example, the following description will be given to the case where a 6-bit information bit string xe2x80x9c01 0101xe2x80x9d is transmitted.
FIG. 3 shows the respective states of the F/F circuits X15 to X0 when the feedback shift register 6 at the transmitter 1 is operated. Upon each receipt of the clock signal CLK, the feedback shift register 6 shifts the values held by the F/F circuits X15 to X0 to the left in the drawing, so that xe2x80x9cSTATExe2x80x9d is incremented by 1 upon each receipt of the clock signal CLK. That is, the individual F/F circuits X15 to X0 undergo transitions from xe2x80x9cSTATE 0xe2x80x9d to xe2x80x9cSTATE 6xe2x80x9d when viewed in the columnar direction.
In xe2x80x9cSTATE 0xe2x80x9d, each of the F/F circuits X15 to X0 is reset to xe2x80x9c0xe2x80x9d.
In xe2x80x9cSTATE 1xe2x80x9d through xe2x80x9cSTATE 6xe2x80x9d shown in FIG. 2, the switch S1 is switched to connect the input signal DIN1 to the output signal DOUT, and the switch 2 is closed. Consequently, the information bit string xe2x80x9c01 0101xe2x80x9d inputted from the input signal DIN1 is inputted to the feedback shift register 6 and outputted simultaneously to the output signal DOUT1.
The information bit string outputted to the output signal DOUT1 is modulated by the data modulating/transmitting unit 5 and then transmitted to the receiver 2 via the radio transmission line 3.
When the feedback shift register 6 has operated to reach xe2x80x9cSTATE 6xe2x80x9d, the values xe2x80x9c0100 0010 0001 0100xe2x80x9d held by the respective F/F circuits X15 to X0 form a check bit string and the cyclic code xe2x80x9c01 0101 0100 0010 0001 0100xe2x80x9d enclosed in the bold rectangle of FIG. 3 are generated from the information bit string and the check bit string.
An output of the check bit string is performed by operating the feedback shift register 6 and sequentially outputting the values held by the F/F circuits X15 to X0 in xe2x80x9cSTATE 6xe2x80x9d to the output signal DOUT1. At this time, the switch S1 is switched to connect the output of the F/F circuit X15 to the output signal DOUT1, and the switch S2 is open. By opening the switch S2, a xe2x80x9c0xe2x80x9d is inputted to each of the F/F circuit X0 and the EOR circuits 12b and 12c. 
The check bit string outputted to the output signal DOUT1 is modulated by the data modulating/transmitting unit 5 and then transmitted to the receiver 2 via the radio transmission line 3.
The data receiving/demodulating unit 7 at the receiver 2 receives the modulated cyclic code (information bit string+check bit string) and sequentially demodulates it to the original cyclic code. The data receiving/demodulating unit 7 inputs the individual bits of the cyclic code to the feedback shift register 9 of the error detector 8 in the order in which they were demodulated.
FIG. 4 shows the respective states of the individual F/F circuits X15 to X0 when the feedback shift register 9 of the error detector 8 is operated. It is to be noted that FIG. 4 shows the operation when the received cyclic code has no error.
In xe2x80x9cSTATE 0xe2x80x9d, each of the F/F circuits X15 to X0 is reset to xe2x80x9c0xe2x80x9d. In xe2x80x9cSTATE 1xe2x80x9d through xe2x80x9cSTATE 22xe2x80x9d, the switch S2 of FIG. 2 is closed. The switch S1 may be switched to either side.
The feedback shift register 9 sequentially receives the cyclic code xe2x80x9c01 0101 0100 0010 0001 0100xe2x80x9d from the input signal DIN2. In xe2x80x9cSTATE 22xe2x80x9d in which the cyclic code has been received up to the least significant bit (hereinafter referred to as LSB) thereof, the values held by the F/F circuits X15 to X0, i.e., the value of the remainder obtained by dividing the received cyclic code by the generator polynomial, is xe2x80x9c0xe2x80x9d when the received data is error-free.
Whether or not the remainder is xe2x80x9c0xe2x80x9d is verified by the right/wrong output unit 10 of FIG. 1. Therefore, the feedback shift register 9 sequentially outputs the values held by the F/F circuits X15 to X0 in xe2x80x9cSTATE 22xe2x80x9d to the output signal DOUT2. At this time, the switch S1 is switched to connect the output of the F/F circuit X15 to the output signal DOUT2, while the switch S2 is open.
The right/wrong output unit 10 sequentially receives from the output signal DOUT2 a 16-bit value, which is the remainder from the division, performs a logical NOR operation with respect to each bit of the received value, and outputs the result of the operation to the error detecting signal FLAG. Accordingly, a xe2x80x9c1xe2x80x9d is outputted to the error detecting signal FLAG if the received cyclic code is correct. If the received cyclic code is erroneous, on the other hand, some of the values held by the F/F circuits X15 to X0 in xe2x80x9cSTATE 22xe2x80x9d shown in FIG. 4 are nonzero. Therefore, a xe2x80x9c0xe2x80x9d is outputted to the error detecting signal FLAG as a result of the NOR operation performed with respect to each of the values held by the F/F circuits X15 to X0. If the error detecting signal FLAG is xe2x80x9c0xe2x80x9d, the receiver 2 discards the received data or gives a retransmission instruction to the transmitter 1.
By thus using the cyclic code, the communication system described above detects errors that have occurred on the data on the radio transmission line 3.
In general, communication systems perform not only the error detection but also the error correction for transmitted data. As an error correcting code for use in the error correction, a block code such as the cyclic code and a convolutional code are known. Since the radio transmission line used in mobile communication or the like has highly variable characteristics depending on geographical features and weather conditions and a burst error due to fading is likely to occur, the convolutional code effective in correcting the burst error is used frequently.
FIG. 5 shows an exemplary communication system that performs the error correction by using the convolutional code. In the communication system, the transmitter 1 has the coder 4, a convolutional coder 13, and the data modulating/transmitting unit 5 which are connected in series, and the receiver 2 has the data receiving/demodulating unit 7, a Viterbi decoder 14, a data processing unit 15, and the error detector 8 which are connected in series. In FIG. 5, the same components as used in FIG. 1 are designated by similar reference numerals.
In the communication system shown in FIG. 5, the detection and correction of errors in data transmitted from the transmitter 1 are performed at the receiver 2.
First, the coder 4 at the transmitter 1 obtains a check bit string from an information bit string to generate a cyclic code and sequentially outputs the cyclic code to the output signal DOUT1 having the information bit string side as the most significant bit (hereinafter referred to as MSB).
The convolutional coder 13 sequentially receives the cyclic code from the MSB side, generates the convolutional code, and outputs the code to the data modulating/transmitting unit 5. The data modulating/transmitting unit 5 modulates the convolutional code and outputs the modulated convolutional code onto the radio transmission line 3.
The data transmitting/demodulating unit 7 at the receiver 2 sequentially receives the modulated convolutional code, demodulates the code to the original convolutional code, and outputs it to the Viterbi decoder 14.
The Viterbi decoder 14 decodes the received convolutional code to the original cyclic code. During decoding, the Viterbi decoder corrects the burst error or the like that has occurred on the radio transmission line 3 to recover the original correct bit string. In the Viterbi decoder 14, the cyclic code is sequentially decoded from the LSB side and outputted.
Next, the cyclic code outputted from the LSB side is sequentially loaded into the data processing unit 15 and, after the reception is completed, the loaded cyclic code is outputted from the MSB side to the input signal DIN2 of the feedback shift register 9. Thereafter, the error detection is performed similarly to that performed by the communication system of FIG. 1 described above and the result of the detection is outputted as the error detecting signal FLAG.
To perform the error detection at the receiver 2 in the communication system shown in FIG. 1, all the bits of the cyclic code should be inputted bit by bit to the error detector 8. If the information bit string has considerable bit length, an increased processing time is required for the error detection, leading to the problem that the error detection process cannot be performed efficiently.
In the communication system shown in FIG. 5, the Viterbi decoder 1 at the receiver 2 decodes the cyclic code from the LSB side. The feedback shift register 9 receives the cyclic code from the MSB side to perform the error detection. Consequently, the receiver 2 cannot output the cyclic code sequentially decoded by the Viterbi decoder 14 directly to the feedback shift register 9.
As a result, the entire cyclic code should preliminarily be inputted from the LSB side to the data processing unit 15 and, after the decoding process by the Viterbi decoder 14 is completed, the cyclic code is finally outputted from the MSB side to the feedback shift register 9.
This causes the problems of the processing time extending from the decoding process to the error detection increasing and the circuit scale increasing.
The increased circuit scale further causes the problem that the chip size of the semiconductor device SEM increases when the error detector 8 has been formed into the semiconductor device SEM.
Since the error detection cannot be performed efficiently, there is the possibility that data transmission efficiency in the communication system is lowered.
It is an object of the present invention, having been made in order to solve the problems described above, to provide an error detector and an error detection method wherein the processing time for error detection can be reduced and errors in transmitted data can be detected efficiently.
Another object of the present invention is to provide a semiconductor device comprising the error detector wherein the error detection can be performed efficiently without increasing the chip size.
Still another object of the present invention is to provide a communication system wherein the error detection can be performed without lowering the efficiency of data transmission on a transmission line.
In the error detector according to the present invention, a feedback shift register for dividing a reception bit string by a generator polynomial is so constructed that a shift direction and a feedback direction in obtaining a remainder thereby are opposite to a shift direction and a feedback direction at a transmitter in generating a transmission bit string by using a specified generator polynomial. Accordingly, the reception bit string is sequentially divided to generate the remainder by inputting the reception bit string to the feedback shift register in reverse order to the transmission bit string was generated at the transmitter. Errors in the reception bit string are detected based on the remainder. This reduces processing time required for the error detection and provides efficient error detection process in the case where the reception bit string is inputted in reverse order to the order the transmission bit string was generated at the transmitter.
In one of the aspects of the present invention, in the error detector, the feedback shift register also comprises: a register unit having stages equal in number to the highest degree of the specified generator polynomial; the first operation unit for performing an operation between an input value to the register unit and an output value from the final stage and outputting a result of the operation to the first stage; and the second operation unit for performing an operation between the output value from the final stage and an output value from the stage equal in number to the degree of each of the terms of the specified generator polynomial other than the highest-degree and lowest-degree terms and outputting a result of the operation to the next stage. Accordingly, the value of the register unit of the feedback shift register in each state is changed to the direction that returns the check bit string generated by the feedback shift register at the transmitter to an initial value, by causing the feedback shift register to perform shift operations and inputting the reception bit string thereto in reverse order of the transmission bit string generated. As a result, the reception bit string can be judged to be erroneous if the value of the register unit when the feedback shift register has performed a specified number of shift operations does not coincide with the initial value of the feedback shift register at the transmitter.
In another aspect of the present invention, the error detector comprises comparing unit for comparing the remainder obtained by the feedback shift register with a predetermined expected value and outputting error data indicative of the dissimilarity as a result of the comparison. This result of the comparison performed by the comparing unit allows easy the error detection. The remainder may be compared bit by bit with the expected value, while causing the feedback shift register performs shift operations, or alternatively, all the bits of the remainder may be compared at a time with the expected value by constructing the feedback shift register such that the generated remainder is outputted in parallel.
In yet another aspect of the present invention, the error detector comprises an initializing unit for initializing the register unit of the feedback shift register. This allows initialization of the register unit without causing the feedback shift register to perform shift operations. As a result, the register unit is loaded with the remainder (check bit string) of the reception bit string, which was generated at the transmitter, by merely causing the feedback shift register to perform shift operations after the initialization. The reason why the reception of the check bit string by the register unit is possible by mere shift operations is that each of the first and second operation units has an input connected to the final stage of the register unit. When the register unit is initialized, therefore, data inputted to the feedback shift register is sequentially loaded therein till it makes a complete circulation around the register unit.
In still another aspect of the present invention, the error detector comprises a specified value setting unit for setting a specified value to the register unit of the feedback shift register. The arrangement allows the remainder (check bit string) obtained at the transmitter to be loaded simultaneously into the register unit without causing the feedback shift register to perform shift operations.
In another aspect of the present invention, the error detector comprises the first and second feedback shift registers. The shift direction and the feedback direction in the first feedback shift register are the same as the shift direction and the feedback direction at a transmitter in generating a transmission bit string by using a specified generator polynomial. A shift direction and a feedback direction in the second feedback shift register are opposite to the shift direction and feedback direction at the transmitter in generating the transmission bit string by using the specified generator polynomial. The first feedback shift register generates a remainder by receiving a reception bit string in the same order in which the transmission bit string was generated at the transmitter and dividing the reception bit string. The second feedback shift register generates a remainder by receiving the reception bit string in reverse order to the transmission bit string was generated at the transmitter and dividing the reception bit string. The error detector detects errors in the reception bit string based on an agreement or a disagreement between the respective remainders obtained by the first and second shift registers.
In still another aspect of the present invention, in the error detector, the first feedback shift register comprises: a first register unit having stages equal in number to the highest degree of the specified generator polynomial; the first operation unit for performing an operation between an input value to the first register unit and an output value from the final stage and outputting a result of the operation to the first stage; and a second operation unit for performing an operation between the result of the operation performed by the first operation unit and an output value from the stage which is smaller by one ordinal number than the degree of each of the terms of the specified generator polynomial other than the highest-degree and lowest-degree terms. The second feedback shift register comprises: a second register unit having stages equal in number to the highest degree of the specified generator polynomial; a third operation unit for performing an operation between an input value to the second register unit and an output value from the final stage and outputting a result of the operation to the first stage; and a fourth operation unit for performing an operation between the output value from the final stage and an output value from the stage corresponding to the degree of each of the terms of the specified generator polynomial other than the highest-degree and lowest-degree terms and outputting a result of each operation to the subsequent stage.
As a result, the value of the first register unit of the first feedback shift register in each state is changed in the same direction as when the feedback shift register at the transmitter performed shift operations by causing the first feedback shift register to perform shift operations and inputting the reception bit string thereto in the same order in which the transmission bit string was generated at the transmitter. The value of the second register unit of the second feedback shift register in each state is changed in the direction that returns the check bit string generated by the feedback shift register at the transmitter to the initial value, by causing the second feedback shift register to perform shift operations and inputting the reception bit string thereto in reverse order to the transmission bit string was generated at the transmitter. If the reception bit string has no errors, the value of the first register unit and the value of the second register unit coincide with each other when each of the first and second feedback shift registers performs shift operations. Whether errors in the reception bit string is present or not is detected based on an disagreement or agreement between the respective remainders obtained by the first and second feedback shift registers.
In still another aspect of the present invention, the error detector comprises comparing unit for comparing the respective remainders obtained by the first and second feedback shift registers and outputting error data indicative of a dissimilarity as a result of the comparison. The arrangement allows the error detection based on the result of the comparison performed by the comparing unit.
In still another aspect of the present invention, the error detector comprises specified value setting unit for setting a specified value to each of the first and second feedback shift registers. The arrangement allows the setting of a specified value to each of the first and second registers without causing the first and second feedback shift registers to perform shift operations.
In one of the aspects of the present invention, in the semiconductor device, each of the foregoing error detectors can be composed of an error detector formed in the semiconductor device with other communication functional elements without increasing the manufacturing cost. Since the feedback shift register composing the error detector has been constructed by merely reversing the shift direction and the feedback direction of the feedback shift register at the transmitter, if the conventional semiconductor device has a feedback shift register of the same construction as that of the feedback shift register at the transmitter, the semiconductor device comprising a feedback shift register which is opposite in shift direction and in feedback direction can be formed easily by merely changing a mask for the wiring layer of the semiconductor device and changing the wiring of the feedback shift register. In this case, there is no need to change the chip size and pad position of the semiconductor device and any changes do not influence on exterior of the semiconductor device.
In one of the aspects of the present invention, in the error detection method, the inputting of a reception bit string to a division procedure using a specified generator polynomial as a divisor is performed in an order reverse to the order in which the transmission bit string was generated at the transmitter by using the generator polynomial. Errors in the reception bit string are detected based on the obtained remainder, which reduces the processing time required for the error detection.
In another aspect of the present invention, in the error detection method, the remainder from the division procedure is compared with a predetermined expected value, the reception bit string is judged to be erroneous when the result of the comparison indicates a dissimilarity therebetween, so that the processing time required for the error detection is reduced.
In yet another aspect of the present invention, in the error detection method, a buffer unit for receiving the remainder from the division procedure is initialized before the division procedure is executed, which reduces the processing time required for the error detection.
In still another aspect of the present invention, in the error detection method, a buffer unit for receiving the remainder from the division procedure is set to a specified value before the division procedure is executed, which reduces the processing time required for the error detection.
In still another aspect of the present invention, in the error detection method, the first and second division procedures each for dividing a reception bit string by a specified generator polynomial are provided. The inputting of the reception bit string to the first division procedure is performed in the same order in which a transmission bit string is generated by using the generator polynomial at the transmitter. On the other hand, the inputting of the reception bit string to the second division procedure is performed in an order reverse to the order in which the transmission bit string is generated by using the generator polynomial at the transmitter. The respective remainders from the first and second division procedures are compared and the reception bit string is judged to be erroneous when the result of the comparison indicates a dissimilarity therebetween.
In another aspect of the present invention, in the error detection method, each of the first buffer unit for receiving the remainder from the first division procedure and the second buffer unit for receiving the remainder from the second division procedure is set to a specified value before the first and second division procedures are executed, so that the processing time required for the error detection is reduced.